/**
 * https://leetcode.cn/submissions/detail/584168051/
 * 1306. 跳跃游戏 III
 * Medium, 黄伟杰 2024.11.30
 * BFS
 */

class Solution
{
public:
    bool canReach(vector<int> &arr, int start)
    {
        int n = arr.size() - 1;
        vector<bool> vis(n + 1, false);
        deque<int> dq; //<下标
        dq.push_back(start);
        while (!dq.empty())
        {
            auto p = dq.front();
            dq.pop_front();
            if (vis[p])
                continue;
            // int i = p;

            int i = arr[p];

            if (p + i <= n)
                if (arr[p + i] != 0)
                    dq.push_back(p + i);
                else
                    return true;
            if (p - i >= 0)
                if (arr[p - i] != 0)
                    dq.push_back(p - i);
                else
                    return true;

            vis[p] = true;
        }
        return false;
    }
};